//
//  22_括号生成.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/14.
/**
 https://leetcode.cn/problems/generate-parentheses/description/
 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

  

 示例 1：

 输入：n = 3
 输出：["((()))","(()())","(())()","()(())","()()()"]
 示例 2：

 输入：n = 1
 输出：["()"]

 */

import UIKit

class KuoHaoDFS: NSObject {
    
    func QA() {
        print(generateParenthesis(0))
    }
    
    func generateParenthesis(_ n: Int) -> [String] {
        if n < 0 { return [] }
        var result = [String]()
        var charArray: [Character] = Array(repeating: " ", count: n << 1)
        dps(0, &result, &charArray, left: n, right: n)
        return result
    }
    func dps(_ index: Int, _ result: inout [String], _ charArray: inout [Character], left: Int, right: Int) {
        if index == charArray.count {
            let str = String(charArray)
            result.append(str)
            return
        }
        
        if left > 0 {
            charArray[index] = "("
            dps(index + 1, &result, &charArray, left: left - 1, right: right)
        }
        
        if right > 0 && right > left {
            charArray[index] = ")"
            dps(index + 1, &result, &charArray, left: left, right: right - 1)
        }
        
    }
    
}
